Một chương trình Prolog bao gồm các luật được biểu diễn dưới dạng mệnh đề Horn. Một mệnh đề Horn có dạng

Head:-Body.

Head là một vị từ logic, còn Body có thể là rỗng hoặc là một tập các vị từ logic. Ví dụ như sau:

chẵn(X):- X chia_dư 2 = 0.

Phần lớn các bộ dịch của các chương trình Prolog đều yêu cầu vị từ logic ở phần đầu của một mệnh đề Horn là một vị từ dương (không có dấu phủ định đi kèm), còn các vị từ trong phần Body có thể có dấu phủ định đi kèm. Chương trình logic mà không có sự xuất hiện của dấu phủ định đi kèm gọi là chương trình logic xác định, còn không thì được gọi là chương trình logic thường.

Dữ kiện

Dữ kiện là những mệnh đề Horn mà phần Body là rỗng. Kiểu mệnh đề này thường được sử dụng để mô tả các dự kiện của bài toán, ví dụ như việc khai báo "tôm" là một con mèo:

mèo(tôm).

Khoảng cách từ Hà Nội vào thành phố Hồ Chí Minh là khoảng 2000Km:

khoảng_cách(Hà_Nội,TP_Hồ_Chí_Minh,2000).

Luật

Phần còn lại của các mệnh đề trong một chương trình Prolog được gọi là luật. Nó thường thể hiện những phát biểu logic trong bài toán, ví dụ như nếu công tắc đèn bật thì đèn sáng:

đèn_sáng(X):- công_tắc_bật(X).

Toán tử ":-" được dịch thô là "nếu", trong logic thì nó đại diện cho toán tử suy ra "<-". Phát biểu trên được phát biểu dưới dạng văn xuôi là "Nếu công tắc của đèn X bật thì đèn X sẽ sáng". Tất nhiên, bạn có thể chưa thoả mãn với phát biểu này và bổ sung vào nó để có một phát biểu chặt chẽ hơn:

đèn_sáng(X):- công_tắc_bật(X), có_điện.

Dấu phẩy "," trong mệnh đề trên được dịch là toán tử "và"; biến trong Prolog được quy ước bắt đầu là một chữ cái hoa.